The present invention is relevant for the field of data bases, especially data base systems handling huge numbers of data. In this connection the patent applications WO 02/061612 A2 and WO 02/061613 A2 disclose—amongst others—such data base systems, data structures used therein and query optimizers for such data base systems. The disclosure of both these applications is incorporated herein by reference. These applications especially reflect storage and query strategies based on balanced binary trees.
Furtheron reference is made to European patent application No. 03 015 365.4 (prior art according to article 54(3) EPC), which basically discloses the method of storing certain query results as bitmaps, which is a very simple and machine-oriented strategy of storing data. Again the contents of this older patent application is incorporated herein by reference.
Now concerning the background of the present invention reference is made to the practical use of data storage systems. Users of such systems enter queries comprising query conditions into the data storage system to get back according result data sets, e.g. including a certain name or date. Especially in case of huge numbers of hits and thus data sets to be returned users commonly want to have a certain sorting so that only a restricted number of hits are presented to them, e.g. the ten youngest persons with the query condition “NAME=Smith”.
Known sorting methods go through the whole result data sets to filter out the required hits according to the given sort attribute, i.e. such sorting can be very time-consuming for such data sets. Generally spoken, if one wants to return only the first ten data sets of a result set of M hits sorted by a particular sort attribute the data storage system must in any case sort the entire result set.